1. Field of the Invention
This invention relates to cache memories for multi-processing systems in which validating bits in the cache for any processor are set and cleared in order to verify that data stored in each cache memory matches data stored in a common main memory. In particular, the invention requires at least two RAM chips for each cache, one of which stores the validating bits associated with the cache until such time that a processor sends an invalidate instruction to an active RAM. Following the invalidate instruction, a previously cleared, or inactive, RAM is switched in to replace the RAM which is to be invalidated (i.e., cleared).
2. Background Art
In multiprocessor systems each of the processors generally has an associated low capacity, low cycle time cache memory and a main memory which is shared by all of the processors. A problem arises in such a system when a main memory address may be resident in one or more processors' dedicated cache memories at any one instant of time and another processor (or other device capable of storing into main memory) stores information into that main memory address in the main memory. If one of the plural processors modifies that data word with a write operation, steps must be taken in order to preserve the integrity of the data to prevent a processor from obtaining a data word from its own dedicated cache which is no longer current because of the write operation performed by a different processor.
Duplicate or ambiguous results must be avoided when data is copied into a requestor's cache memory if that data word has been modified in the shared main memory by a different requestor. Other processors in the system must be prevented from utilizing invalid data words which may be resident in their dedicated cache memories. This may be accomplished through the addition of a write monitoring apparatus which is associated with each dedicated cache memory in the system. The write monitoring apparatus monitors traffic on the system's main memory buses and when it detects a match in address with a data word contained in its associated dedicated cache memory, it clears, (or sets), a bit in a "valid flag directory" which causes the processor associated with that cache memory, when attempting to read that data word from that dedicated cache, to recognize the data word as being invalid. The processor will retrieve the desired data word from the main memory where it has been modified, instead of obtaining the word directly from its associated cache memory.
By this technique, each processor dedicated cache will only indicate resident data as "valid" if that data had been previously placed in the data cache and had not yet been modified in main memory by another requestor's actions. Therefore, cache contents are current, in real time, within the normal timing uncertainties and granularities of a shared main memory, multiprocessor, computer system. To ensure that totally unambiguous validity semaphore actions, e.g., Test and Set, are properly performed, the replace cycle involves (1) a read direct from main memory, bypassing the cache memory, (2) modification including the setting or clearing of the semaphore part of the operand word, and (3) writing of the updated words utilizing the main memory. The write portion of the replace cycle is monitored by other dedicated cache memories in a normal write cycle which, therefore, ensures that the other dedicated cache memories are informed of the semaphore up-date.
The sequence of events resulting in the address invalidation of a data word in a given requestor's (Requestor A) cache because of another requestor's (Requestor B) write operation into main memory at that same address is as follows:
First, let it be assumed that Requestor A has requested and used a data word at address, y, in main memory, leaving the data word in Requestor A's cache and the address, y, in both its associated Primary and Duplicate Cache Directories. Then, as Requestor B initiates a memory sequence (write) to modify the data word in main memory at address, y, it supplies the address, y, on the memory bus as it activates its "memory initiate" and "write" control lines. The monitor of Requestor A monitors all of the ports into main memory (except its own) and so when it determines that Requestor B has activated a memory "write" operation, the address associated with that "write" operation is captured by being latched into a register and compared with the addresses currently resident in Requestor A's Cache Directory.
Under the assumed conditions, a compare will be found and a conflict search "hit" is made. The resulting hit signal is used to clear the "valid" flag associated with that directory location containing the address, y. Both a true address compare and the "valid flag set" condition are required for a resident data hit condition when a requestor references its cache memory for a data word. In the above case, when Requestor A references its cache memory for the data word at address, y, it will find the address compare upon a search of its cache directory, but will be forced to fetch the data word from the main memory because the "valid flag" will now not be set. In this way, Requestor A will now not be set. In this way, Requestor A will receive the current, unambiguous data from the system's main memory.